package linkedlist.test109;

import listbyorder.utils.ListNode;
import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/14 13:51
 */
public class Solution1 {

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        if (head.next.next == null) {
            TreeNode root = new TreeNode(head.val);
            root.right = new TreeNode(head.next.val);
            return root;
        }
        // 首先快慢指针找到中间节点
        ListNode s = head, f = head.next.next;
        while (f != null && f.next != null) {
            s = s.next;
            f = f.next.next;
        }
        ListNode r = s.next.next;
        TreeNode root = new TreeNode(s.next.val);
        s.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(r);
        return root;
    }
}
